package getOffer.offer59_1;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wjy
 * @Date: 2021/11/27 17:05
 */
public class Solution {

    public static void main(String[] args) {

        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        //int[] nums = {1, -1};

        Solution solution = new Solution();
        int[] ints = solution.maxSlidingWindow2(nums, 3);

        for (int i : ints) {
            System.out.println(i);
        }

    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[0];
        }

        int max = nums[0], temp = 0, index = 0;
        int[] res = new int[nums.length - k + 1];

        for (int right = k; right <= nums.length; right++) {
            max = nums[right - k];
            for (int left = right - k; left < right; left++) {
                temp = nums[left];
                max = Math.max(max, temp);
            }

            res[index++] = max;
        }

        return res;
    }

    public int[] maxSlidingWindow2(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
            // 删除 deque 中对应的 nums[i-1]
            if(i > 0 && deque.peekFirst() == nums[i - 1])
                deque.removeFirst();
            // 保持 deque 递减
            while(!deque.isEmpty() && deque.peekLast() < nums[j])
                deque.removeLast();
            deque.addLast(nums[j]);
            // 记录窗口最大值
            if(i >= 0)
                res[i] = deque.peekFirst();
        }
        return res;
    }

}
